package chapter13;

/*
    Searching.java            Java Foundations.

    Contains various search algorithms that operate on an array of Comparable objects..
 */

public class Searching {
    /*
        Searches the specified array of objects using a linear search
        algorithm. Returns null if the target os not found.
     */
    public static int linearSearch ( int [] data,int target){
        int  result = 0;
        int index = 0;

        while (result == 0 && index < data.length){
            if (data[index] - (target) == 0)
                result = data[index];
            index++;
        }
        return result;
    }

    /*
        Searches the specified array of objects using a binary search
        algorithm. Returns null if the target is not found.
     */
    public static int binarySearch (int[] data,
                                           int target){
        int result = 0;
        int first = 0, last = data.length-1, mid;

        while (result == 0 && first <= last){
            mid = (first + last ) / 2;  //   determine midpoint
            if(data[mid]-target==0)
                result = data[mid];
            else if (data[mid]-(target) > 0)
                last = mid - 1;
            else
                first = mid + 1;
        }
        return result;
    }
    public static int blockSearch(int[] index, int[] st, int key, int m) {
        int i = binarySearch(index, key);
        if (i >= 0) {
        int j = i > 0 ? i * m : i;
        int len = (i + 1) * m;
        // 在确定的块中用顺序查找方法查找key
        for (int k = j; k < len; k++) {
            if (key == st[k]) {
                System.out.println("查询成功");
                return k;
            }
        }
    }
    System.out.println("查找失败");
    return -1;
}
}
